<?php
/**
 ***** 扶摇而上、抱守本真 ******
 * @author Dana
 * @Date 2021/7/13
 */

class TreeNode{
    public $val = null;
    public $left = null;
    public $right = null;
    public function __construct($val = 0,$left = null,$right = null)
    {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}


class solution{
    /**
     * 后续遍历的最后一个数字是根节点
     * 中序遍历的根节点，左边是左子树，右边是右子树
     */

    public function buildTree($inOrder,$postOrder)
    {
        if(empty($postOrder)) return null;

        $tree = new TreeNode(end($postOrder));

        $leftCnt = 0;// 左子树元素计算器
        while($inOrder[$leftCnt] != end($postOrder)) $leftCnt++;

        // 构建左子树的中序和后续数组
        $tree->left = $this->buildTree(array_slice($inOrder,0,$leftCnt),array_slice($postOrder,0,$leftCnt));
        $tree->right = $this->buildTree(array_slice($inOrder,1+$leftCnt),array_slice($postOrder,$leftCnt,-1));
        return $tree;
    }

    public function seBuildTree($inOrder,$postOrder)
    {
        $postOrderLen = count($postOrder);
        if(empty($postOrder)) return null;
        // 根节点
        $root = new TreeNode(end($postOrder));
        $stack =new SplStack();
        $stack->push($root);

        $inOrderIndex = count($inOrder) -1;
        for($i = $postOrderLen -2;$i >=0;$i--){
            $postOrderVal = $postOrder[$i];
            $node = $stack->top();

            if($node->val != $inOrder[$inOrderIndex]){
                $node->right = new TreeNode($postOrderVal);
                $stack->push($node->right);
            }else{
                while(!$stack->isEmpty() && $stack->top()->val == $inOrder[$inOrderIndex]){
                    $node = $stack->pop();
                    $inOrderIndex--;
                }
                $node->left = new TreeNode($postOrderVal);
                $stack->push($node->left);
            }
        }
        return $root;
    }

    public function prebuildTree($preOrder,$inOrder)
    {
        if(empty($preOrder)) return null;
        $val = current($preOrder);
        $tree = new TreeNode($val);
        $offset = array_search($val,$inOrder);
        reset($preOrder);
        $tree->left = $this->prebuildTree(array_slice($preOrder,1,$offset), array_slice($inOrder,0,$offset));
        $tree->right = $this->prebuildTree(array_slice($preOrder, $offset+1), array_slice($inOrder, $offset+1));
        return $tree;
    }

}


//$preOrder = [3,9,6,10,20,15,7];
$preOrder = [3,9,20,15,7];

var_dump(array_shift($preOrder));die;
//$inOrder = [6,9,10,3,15,20,7];
$inOrder = [9,3,15,20,7];

$postOrder = [6,10,9,15,7,20,3];

$object = new solution();

$res = $object->prebuildTree($preOrder,$inOrder);
var_export($res);

//$res1 = $object->seBuildTree($inOrder,$postOrder);
//var_dump($res1);
